public class LeetCode020 {
    private interface Stack<E> {
        int getSize();
        boolean isEmpty();
        void push(E e);
        E pop();
        E peek();
    }

    private class ArrayStack<E> implements Stack<E> {
        // 使用上一章定义好的动态数组
        Array<E> array;

        public ArrayStack(int capacity){
            array = new Array<>(capacity);
        }

        public ArrayStack(){
            array = new Array<>();
        }

        @Override
        public int getSize() {
            return array.getSize();
        }

        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }

        @Override
        public void push(E e) {
            array.addLast(e);
        }

        @Override
        public E pop() {
            return array.removeList();
        }

        @Override
        public E peek() {
            return array.getList();
        }

        public int getCapacity(){
            return array.getCapacity();
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Stack: ");
            res.append("[");
            for (int i = 0; i < array.getSize(); i++) {
                res.append(array.get(i));
                if (i!=array.getSize()-1){
                    res.append(", ");
                }
            }
            // 显示的指示出哪里是栈顶
            res.append("] top");
            return res.toString();
        }
    }

    private class Array<E> {
        private E[] data;
        private int size;           //当前数组中第一个没有元素的位置&&元素个数

        /**
         * 初始化一个数组
         *
         * @param capacity 数组最大容量
         */
        public Array(int capacity) {
            data = (E[]) new Object[capacity];
            size = 0;
        }

        /**
         * 无参构造默认10
         */
        public Array() {
            this(10);
        }

        /**
         * 获取数组中元素个数
         */
        public int getSize() {
            return size;
        }

        /**
         * 获取数组容量
         */
        public int getCapacity() {
            return data.length;
        }

        /**
         * 返回数组是否为空
         */
        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 向所有元素最后添加一个新元素
         *
         * @param e
         */
        public void addLast(E e) {
            add(size, e);
        }

        /**
         * 头添加
         *
         * @param e
         */
        public void addFirst(E e) {
            add(0, e);
        }

        /**
         * 在index位置插入新元素e
         *
         * @param index
         * @param e
         */
        public void add(int index, E e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
            }
            if (size == data.length) {
                resize(2*data.length);
            }
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }

        /**
         * 改变当前容量大小
         * @param newCapacity
         */
        private void resize(int newCapacity) {
            E[] newData = (E[])new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            data = newData;
        }

        /**
         * 打印数组
         *
         * @return
         */
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
            res.append("[");
            for (int i = 0; i < size; i++) {
                res.append(data[i]);
                if (i != size - 1)
                    res.append(", ");
            }
            res.append("]");
            return res.toString();
        }

        /**
         * 获取
         *
         * @param index
         * @return
         */
        E get(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("Get failed. Index is illegal.");
            }
            return data[index];
        }

        /**
         * 取出第一个元素
         * @return
         */
        E getFirst(){
            return get(0);
        }

        /**
         * 取出最后一个元素
         * @return
         */
        E getList(){
            return get(size-1);
        }


        /**
         * 修改元素
         *
         * @param index
         * @param e
         */
        void set(int index, E e) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("Set failed. Index is illegal.");
            }
            data[index] = e;
        }

        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i] == e) {
                    return true;
                }
            }
            return false;
        }

        public int find(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i] == e) {
                    return i;
                }
            }
            return -1;
        }

        /**
         * 从数组中删除元素，并返回
         *
         * @param index
         * @return
         */
        public E remove(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
            }
            E ret = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null;  //loitering objects != memory leak
            //如果数据量只有容量的一半，缩容。为了防止复杂度振荡，当数组元素为容量的四分之一时才缩容为一半
            if (size==data.length / 4 && data.length /2 != 0){
                resize(data.length/2);
            }
            return ret;
        }

        /**
         * 从数组中删除第一个元素
         *
         * @return
         */
        public E removeFirst() {
            return remove(0);
        }

        /**
         * 从数组中删除最后一个元素
         *
         * @return
         */
        public E removeList() {
            return remove(size - 1);
        }

        /**
         * 从数组中删除元素e
         *
         * @param e
         */
        public void removeElement(E e) {
            int index = find(e);
            if (index != -1) {
                remove(index);
            }
        }
    }

    public static void main(String[] args) {
        LeetCode020 leetCode020 = new LeetCode020();

        System.out.println(leetCode020.isValid("[]"));
        System.out.println(leetCode020.isValid("[)(]"));
        System.out.println(leetCode020.isValid("[(]"));
        System.out.println(leetCode020.isValid("[()]"));
        System.out.println(leetCode020.isValid("[({})]"));

    }
    public boolean isValid(String s) {
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '['){
                stack.push(c);
            }else{
                if (stack.isEmpty()){
                    return false;
                }
                char top = stack.pop();
                if (c == ')' && top != '('){
                    return false;
                }
                if (c == ']' && top != '['){
                    return false;
                }
                if (c == '}' && top != '{') {
                    return false;
                }
            }
        }
        // 如果遍历完括号之后栈里没有元素则证明所有都匹配了
        return stack.isEmpty();
    }
}

